Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S.
You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
题目大意：寻找给定字符串（长度不超过1000）的最长回文子串，回文子串存在且唯一
题目难度：Medium
/**
* Created by gzdaijie on 16/5/3
* 回文字符串只有2种形式, abba,aba
* (1) 遍历字符,查看其左右是否相等, 更新start,end
* (2) 遍历字符,如果右边与当前字符相等,查看这2个字符的左右是否相等, 更新start,end
* 若最长回文串长度为K,最坏复杂度为O(K*N)
*/
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
int start = 0, end = 0;
for (int i = 0; i < len; ++i) {
// 情况1: aba,奇数回文串
int k = 1;
while (i - k >= 0 && i + k < len && s.charAt(i - k) == s.charAt(i + k)) ++k;
if (end - start < 2 * k - 1) {
start = i - k + 1;
end = i + k;
}
// 情况2: abba,偶数回文串
k = 0;
while (i - k >= 0 && i + k + 1 < len && s.charAt(i - k) == s.charAt(i + k + 1)) ++k;
if (end - start < 2 * k) {
start = i - k + 1;
end = i + k + 1;
}
}
return s.substring(start, end);
}
}
/**
* Created by gzdaijie on 16/5/3
* 首先所有字符都相同的字符串无论字符多少,都是回文字符串
* 对于有连续相等的字符的字符串, zxyyyyyyxa,只需找到连续相等的y的第一个和最后一个位置,判断左右即可
* 遍历时,可直接从第一个y的位置跳到最后一个y下一位
* 当字符有1000个，连续出现同一字符概率很大，因此此算法非常高效，但是若无连续出现字符，仍为O(N*K)
*/
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
int max = 0;
int start = 0;
int end = 0;
for (int i = 0; i < len;) {
int index = this.getFarestSameChar(s, i);
int dist = this.getDistance(s,i ,index);
int p = i - dist;
int q = index + dist;
if (q - p + 1 > max) {
start = p;
end = q;
max = end - start + 1;
}
i = index + 1; // 从i->index的字符都是相等的,因此可以直接跳过
}
return s.substring(start, end + 1);
}
/**
* 判断左右是回文字符的个数
*/
private int getDistance(String s, int start, int end) {
int len = s.length();
int dist = 0;
start -= 1;
end += 1;
while (start >= 0 && end < len) {
if (s.charAt(start) != s.charAt(end)) break;
--start;
++end;
++dist;
}
return dist;
}
/**
* 连续字符,最远的一个下标
*/
private int getFarestSameChar(String s, int index) {
int len = s.length();
char ch = s.charAt(index);
for (int i = index + 1; i < len; ++i) {
if (ch != s.charAt(i))return i - 1;
}
return len - 1;
}
}
/**
* Created by gzdaijie on 16/5/4
* Manacher 算法
* 使用#扩展字符串解决奇偶回文字符串问题
* 使用数组RL和对称中心pos,避免重复计算
* 复杂度O(N)，分析见参考
* 但是在leetcode上运行时间超过以上2种，原因未知
*/
public class Solution {
public String longestPalindrome(String s) {
String str = this.addSharpToString(s);
int len = str.length();
int max, start, end;
int maxRight, pos;
int[] RL = new int[len];
max = start = end = maxRight = pos = 0;
for (int i = 0; i < len; ++i) {
// 如果i在maxRight的左边,初始值设置为i的对称位的值
if (i < maxRight) {
RL[i] = Math.min(RL[2 * pos - i], maxRight - i + 1);
} else {
RL[i] = 1;
}
// 尝试对i进行扩展
while (i - RL[i] >= 0 && i + RL[i] < len) {
if (str.charAt(i - RL[i]) != str.charAt(i + RL[i])) break;
RL[i]++;
}
// 更新最大右边界与对称中心
if (i + RL[i] - 1 > maxRight) {
maxRight = RL[i] + i - 1;
pos = i;
}
// 更新 max与首末位置
if (RL[i] > max) {
max = RL[i];
start = i- RL[i] + 1;
end = i + RL[i] - 1;
}
}
// 去掉#,连接字符串并返回
String result = "";
String[] strings = str.substring(start, end + 1).split("#");
len = strings.length;
for (int i = 0; i < len; i++) {
result += strings[i];
}
return result;
}
private String addSharpToString(String s) {
int len = s.length();
String str = "#";
for (int i = 0; i < len; ++i) {
str += s.charAt(i) + "#";
}
return str;
}
}